	#include <iostream>
	using namespace std;
	// 回溯函数，用于尝试放置皇后
	void backtrack(int row, int n, int& cols, int& leftDiag, int& rightDiag, int& count) {
		if (row == n) {
			// 找到一种解法，解法数量加1
//			printf("%d皇后有%d种解法\n", n, count++);
			count++;
			return;
		}
		
		for (int col = 0; col < n; col++) {
			int colMask = (1 << col);
			int leftDiagMask = (1 << (row + col));
			int rightDiagMask = (1 << (n - 1 - row + col));
			
			// 判断当前位置是否可以放置皇后
//			if ((cols & colMask) || (leftDiag & leftDiagMask) || (rightDiag & rightDiagMask)) {
//				continue;
//			}
			
			// 更新cols、leftDiag和rightDiag的位信息
			cols |= colMask;
			leftDiag |= leftDiagMask;
			rightDiag |= rightDiagMask;
			
			// 递归调用backtrack函数，放置下一行的皇后
			backtrack(row + 1, n, cols, leftDiag, rightDiag, count);
			
			// 恢复cols、leftDiag和rightDiag的位信息，以便尝试其他列的放置
			cols &= ~colMask;
			leftDiag &= ~leftDiagMask;
			rightDiag &= ~rightDiagMask;
		}
	}
	// 计算N皇后问题的解法数量1
	int totalNQueensmain(int n) {
		int count = 0;
		int cols = 0;
		int leftDiag = 0;
		int rightDiag = 0;
		backtrack(0, n, cols, leftDiag, rightDiag, count);
		return count;
	}
	
	
	int main(){
		int n;
		cin >> n;
		printf("%d皇后共有%d种解法",n,totalNQueensmain(n));
	//	totalNQueensmain(20);
		
		return 0;
	}
